DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2020.8

A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains

Authors: David N. Jansen, Jan Friso Groote, Ferry Timmers, and Pengfei Yang

Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)

Abstract

This article improves the time bound for calculating the weak/branching bisimulation minimisation quotient on state-labelled discrete-time Markov chains from O(m n) to an expected-time O(m log⁴ n), where n is the number of states and m the number of transitions. For these results we assume that the set of state labels AP is small (|AP| ∈ O(m/n log⁴ n)). It follows the ideas of Groote et al. (ACM ToCL 2017) in combination with an efficient algorithm to handle decremental strongly connected components (Bernstein et al., STOC 2019).

Cite as

David N. Jansen, Jan Friso Groote, Ferry Timmers, and Pengfei Yang. A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.CONCUR.2020.8,
  author =	{Jansen, David N. and Groote, Jan Friso and Timmers, Ferry and Yang, Pengfei},
  title =	{{A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Konnov, Igor and Kov\'{a}cs, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.8},
  URN =		{urn:nbn:de:0030-drops-128209},
  doi =		{10.4230/LIPIcs.CONCUR.2020.8},
  annote =	{Keywords: Behavioural Equivalence, weak Bisimulation, Markov Chain}
}

Document

DOI: 10.4230/DagSemProc.07101.3

07101 Working Group Report – Performance Measures Other Than Time

Authors: Lucia Cloth, Pepijn Crouzen, Matthias Fruth, Tingting Han, David N. Jansen, Mark Kattenbelt, Gerard J. M. Smit, and Lijun Zhang

Published in: Dagstuhl Seminar Proceedings, Volume 7101, Quantitative Aspects of Embedded Systems (2007)

Abstract

This presentation shows a few possible performance measures that might be interesting and possible evaluation methods.

Cite as

Lucia Cloth, Pepijn Crouzen, Matthias Fruth, Tingting Han, David N. Jansen, Mark Kattenbelt, Gerard J. M. Smit, and Lijun Zhang. 07101 Working Group Report – Performance Measures Other Than Time. In Quantitative Aspects of Embedded Systems. Dagstuhl Seminar Proceedings, Volume 7101, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cloth_et_al:DagSemProc.07101.3,
  author =	{Cloth, Lucia and Crouzen, Pepijn and Fruth, Matthias and Han, Tingting and Jansen, David N. and Kattenbelt, Mark and Smit, Gerard J. M. and Zhang, Lijun},
  title =	{{07101 Working Group Report – Performance Measures Other Than Time}},
  booktitle =	{Quantitative Aspects of Embedded Systems},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7101},
  editor =	{Boudewijn Haverkort and Joost-Pieter Katoen and Lothar Thiele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07101.3},
  URN =		{urn:nbn:de:0030-drops-11396},
  doi =		{10.4230/DagSemProc.07101.3},
  annote =	{Keywords: }
}

Search Results

Documents authored by Jansen, David N.

A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains

Abstract

Cite as

07101 Working Group Report – Performance Measures Other Than Time

Abstract

Cite as

Thanks for your feedback!

Could not send message